home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.02 Feb 93 / Programmers' Challenge / UniqueRGBValues.c
Encoding:
Text File  |  1992-12-06  |  6.6 KB  |  210 lines  |  [TEXT/MPS ]
  1. //////////////////////////////////////////////////////////////////////////
  2. //    UniqueRGBValues.c:    A function that returns the number of unique
  3. //                                colors found in a direct RGB formatted image.
  4. //    _______________________________________________________________________
  5. //                             Copyright © 1992
  6. //                           Thomas W. Pinkerton.
  7. //                           All rights reserved.
  8. //
  9. //
  10. // Solution for the November/December 1992
  11. // MacTutor Programmers' Challenge
  12. //
  13. // Author:    Tom Pinkerton
  14. //                426 1/2 Ridge Road
  15. //                Wilmette, IL.  60091
  16. //
  17. //                Phone:        (708) 251-6733
  18. //                FAX:            (708) 251-6737
  19. //
  20. //                AppleLink:    TPINKERTON
  21. //                A Online:    TomPnk
  22. //                CompuServe:    [71041,144]
  23. //
  24. //    _______________________________________________________________________
  25. //////////////////////////////////////////////////////////////////////////
  26.  
  27. unsigned long    UniqueRGBValues(Ptr baseAddress, short numRows, short numCols);
  28.  
  29. //////////////////////////////////////////////////////////////////////////
  30.  
  31. unsigned long UniqueRGBValues(Ptr    baseAddress,
  32.                                         short    numRows,
  33.                                         short    numCols)
  34.  
  35. {
  36.     Handle    sBuffers = nil;
  37.     long        sUniquePixels = 0;
  38.  
  39.     //• Allocate memory for the data structures.
  40.     //• We will need:
  41.     //• 
  42.     //•     256 x 4 bytes for the unique blue value table.
  43.     //•     256 x 256 x 8 bytes for the Red/Green intersection grid.
  44.     //•     numRows x numCols x 4 bytes for the master blue list.
  45.     //• 
  46.     sBuffers = NewHandle((((long)numRows * (long)numCols) * 4L) + 525312);
  47.     if (sBuffers != nil) {
  48.         
  49.         //• Setup pointers to the data structures.
  50.         long*    sBluListPtr = (long*)((char*)*sBuffers + 0);
  51.         long*    sRGTablePtr = (long*)((char*)*sBuffers + 1024);
  52.         long*    sRGLinksPtr = (long*)((char*)*sBuffers + 525312);
  53.         long*    sRGBase = nil;
  54.         
  55.         //• Initialize the Red/Green intersection grid and
  56.         //• the master Blue list with -1's.
  57.         {
  58.             register long*    sInitPtr;
  59.             register long    i;
  60.             
  61.             //• A -1 in this table means that the blue value for
  62.             //• a particular Red/Green combination is not yet found.
  63.             sInitPtr = sBluListPtr;
  64.             i = 64;
  65.             while (i--) {
  66.                 sInitPtr[3] =
  67.                 sInitPtr[2] =
  68.                 sInitPtr[1] =
  69.                 sInitPtr[0] = -1;
  70.                 sInitPtr += 4;
  71.             }
  72.             
  73.             //• Only the blue list link need be initialized (first
  74.             //• of two longs) for each element.  A -1 means that a
  75.             //• unique Red/Green pair represented by this intersection
  76.             //• has not yet been found.
  77.             sInitPtr = sRGTablePtr;
  78.             i = 4096;
  79.             while (i--) {
  80.                 sInitPtr[30] =
  81.                 sInitPtr[28] =
  82.                 sInitPtr[26] =
  83.                 sInitPtr[24] =
  84.                 sInitPtr[22] =
  85.                 sInitPtr[20] =
  86.                 sInitPtr[18] =
  87.                 sInitPtr[16] =
  88.                 sInitPtr[14] =
  89.                 sInitPtr[12] =
  90.                 sInitPtr[10] =
  91.                 sInitPtr[ 8] =
  92.                 sInitPtr[ 6] =
  93.                 sInitPtr[ 4] =
  94.                 sInitPtr[ 2] =
  95.                 sInitPtr[ 0] = -1;
  96.                 sInitPtr += 32;
  97.             }
  98.         }
  99.         
  100.         //• Scan the image to create a linked list of blue values at
  101.         //• each unique Red/Green intersection.  Each element in the
  102.         //• Red/Green intersection grid consists of the first link
  103.         //• of that intersection's blue list (initially -1) and a link
  104.         //• to the next Red/Green intersection which contains a blue
  105.         //• list.  Whereas the Red/Green link is a pointer to the next
  106.         //• Red/Green intersection, a blue list link holds an array index
  107.         //• in its low order 3 bytes and an actual blue value in its
  108.         //• high order byte.  The blue link index refers to an element
  109.         //• in the master blue list.  Each master blue list element then
  110.         //• points to the next blue value link within a specific blue
  111.         //• list or terminates the list with a -1 value.
  112.         {
  113.             register unsigned char*    sPixelsPtr = (unsigned char*)baseAddress;
  114.             register long*                sRGPtr;
  115.             register long*                sLinkPtr = sRGLinksPtr;
  116.             register long                sLinkIndex = 0;
  117.             register long                sNumPixels = (long)numRows * (long)numCols;
  118.             
  119.             //• For each pixel in the image, do the following.
  120.             while (sNumPixels--) {
  121.                 
  122.                 //• Concatenate the red and green values to create
  123.                 //• an offset used to point at the unique Red/Green
  124.                 //• element in the Red/Green intersection grid.
  125.                 sRGPtr = sRGTablePtr + ((((long)sPixelsPtr[1] << 8) |
  126.                                                   (long)sPixelsPtr[2]) << 1);
  127.                 
  128.                 //• If this is the first pixel with this particular
  129.                 //• Red/Green combination, then add the Red/Green
  130.                 //• intersection to the Red/Green linked list.
  131.                 if (sRGPtr[0] == -1) {
  132.                     sRGPtr[1] = (long)sRGBase;
  133.                     sRGBase = sRGPtr;
  134.                 }
  135.                 
  136.                 //• Create a new blue link with the pixel's blue value
  137.                 //• and add it to Red/Green intersection's blue list.
  138.                 *sLinkPtr = sRGPtr[0];
  139.                 sRGPtr[0] = sLinkIndex | ((long)sPixelsPtr[3] << 24);
  140.                 
  141.                 //• Increment stuff for the next go 'round.
  142.                 ++sLinkPtr;
  143.                 ++sLinkIndex;
  144.                 sPixelsPtr += 4;
  145.             }
  146.         }
  147.         
  148.         //• For each list of blue values at a unique Red/Green
  149.         //• intersection, determine the number of unique blue
  150.         //• values in that list.  This calculates the number of
  151.         //• unique colors that have the same Red and Green values.
  152.         //• Accumulating the number of unique colors at every
  153.         //• Red/Green intersection gives us the total number of
  154.         //• unique colors.
  155.         {
  156.             register long*    sRGPtr = sRGBase;
  157.             register long*    sBlueBase = nil;
  158.             register long*    sBluePtr;
  159.             register long    sLinkIndex;
  160.             
  161.             //• For each Red/Green intersection found above,
  162.             //• do the following.
  163.             while (sRGPtr != nil) {
  164.                 
  165.                 //• Walk the list of blue values for this Red/Green pair.
  166.                 //• For each one, do the following.
  167.                 sLinkIndex = sRGPtr[0];
  168.                 while (sLinkIndex != -1) {
  169.                     
  170.                     //• Create a pointer to the unique blue value element.
  171.                     sBluePtr = sBluListPtr + ((unsigned long)sLinkIndex >> 24);
  172.                     
  173.                     //• A -1 here means that the unique R/G and B color has
  174.                     //• not yet been counted.  Therefore, mark the fact that
  175.                     //• it has been counted by adding the element to a linked
  176.                     //• list and incrementing the unique color count.  The
  177.                     //• blue value linked list is used later to quickly reset
  178.                     //• itself.
  179.                     if (*sBluePtr == -1) {
  180.                         *sBluePtr = (long)sBlueBase;
  181.                         sBlueBase = sBluePtr;
  182.                         ++sUniquePixels;
  183.                     }
  184.                     
  185.                     //• Get the next blue list link in the blue list.
  186.                     sLinkIndex = sRGLinksPtr[sLinkIndex & 0x00FFFFFF];
  187.                 }
  188.                 
  189.                 //• Reset the blue count list by walking its links and
  190.                 //• replacing them again with -1's.
  191.                 sBluePtr = sBlueBase;
  192.                 while (sBluePtr != nil) {
  193.                     sBlueBase = (long*)*sBluePtr;
  194.                     *sBluePtr = -1;
  195.                     sBluePtr = sBlueBase;
  196.                 }
  197.                 sBlueBase = nil;
  198.                 
  199.                 //• Get next Red/Green intersection.
  200.                 sRGPtr = (long*)sRGPtr[1];
  201.             }
  202.         }
  203.         
  204.         DisposHandle(sBuffers);
  205.     }
  206.     return(sUniquePixels);
  207. }
  208.  
  209. //////////////////////////////////////////////////////////////////////////
  210.